package com.lark.algorithm.train.onChapter.linkedList;

/**
 * @author btmood
 * @version 1.0
 * @apiNote
 * Q1290：二进制链表转整数
 * 给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
 *
 * 请你返回该链表所表示数字的 十进制值 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：head = [1,0,1]
 * 输出：5
 * 解释：二进制数 (101) 转化为十进制数 (5)
 * 示例 2：
 *
 * 输入：head = [0]
 * 输出：0
 * 示例 3：
 *
 * 输入：head = [1]
 * 输出：1
 * 示例 4：
 *
 * 输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
 * 输出：18880
 * 示例 5：
 *
 * 输入：head = [0,0]
 * 输出：0
 *
 *
 * 提示：
 *
 * 链表不为空。
 * 链表的结点总数不超过 30。
 * 每个结点的值不是 0 就是 1。
 * @since 2024-05-17 10:48
 */
public class D20240517Q1290_二进制链表转整数 {

    /**
     * 反转链表，根据二进制的位数进行累加
     * @param head
     * @return
     */
    public int getDecimalValue(ListNode head) {
        ListNode newHead = reverseOnHead(head);
        ListNode cur = newHead;
        int i = 0;
        int count = 0;
        while (cur != null) {
            count = count + cur.val * (int) (Math.pow(2, i++));
            cur = cur.next;
        }
        return count;
    }

    // 虚拟头节点反转
    private ListNode reverseOnHead(ListNode head) {
        ListNode dummyHead = new ListNode();
        ListNode cur = head;
        while (cur != null) {
            ListNode nextNode = cur.next;
            cur.next = dummyHead.next;
            dummyHead.next = cur;
            cur = nextNode;
        }
        return dummyHead.next;
    }

    // 递归反转
    private ListNode reverseOnRecursion(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode reversedLinkedList = reverseOnRecursion(head.next);
        head.next.next = head;
        head.next = null;
        return reversedLinkedList;
    }

    public int getDecimalValue2(ListNode head) {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count = count * 2 + cur.val;
            cur = cur.next;
        }
        return count;
    }

    public int getDecimalValue3(ListNode head) {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count = count << 2 + cur.val;
            cur = cur.next;
        }
        return count;
    }


    int res = 0;
    int count = 0;
    public int getDecimalValue4(ListNode head) {
        if (head == null) {
            return 0;
        }
        // 如何拆分问题呢？
        // head节点的值 + 后续递归；head节点的值应该写成什么？
        res += (int) (getDecimalValue4(head.next) + head.val * Math.pow(2, count++));
        return res;
    }





    public static void main(String[] args) {
        D20240517Q1290_二进制链表转整数 m = new D20240517Q1290_二进制链表转整数();
        ListNode l1 = new ListNode(5);
        ListNode l2 = new ListNode(4, l1);
        ListNode l3 = new ListNode(3, l2);
        ListNode l4 = new ListNode(2, l3);
        ListNode l5 = new ListNode(1, l4);
        System.out.println(l5);
        ListNode listNode = m.reverseOnHead(l5);
        System.out.println(listNode);
        int[] tenArr = new int[]{1,2,3,4,5,6};
    }

    public static class  ListNode {
        int val;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
        ListNode next;

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            ListNode cur = next;
            sb.append(val);
            while (cur != null) {
                sb.append("=>");
                sb.append(cur.val);
                cur = cur.next;
            }
            return sb.toString();
        }
    }
}


